/**
 * 汉诺塔问题
 *
 * @Author: wanqian
 * @Date: 2021/2/26 11:05
 */
public class HanoiTowerDemo {
    /**
     * 移动次数
     */
    public static long count = 0;

    public static void main(String[] args) {
        hanoiTower(5, 'a', 'b', 'c');
        System.out.println(count);
    }

    /**
     * 汉诺塔问题
     *
     * @param num 盘子的数量
     * @param a   起始柱子
     * @param b   辅助柱子
     * @param c   目标柱子
     */
    public static void hanoiTower(int num, char a, char b, char c) {
        if (num == 1) {
            count++;
            System.out.println(String.format("第%d个盘从%c -> %c", num, a, c));
        } else {
            //将汉诺塔问题分解成类似两个盘的情况，将上面num-1个盘都看成是一个盘子
            //1. 将上面num-1个盘子由a柱移动到b柱
            hanoiTower(num - 1, a, c, b);
            //2. 将最下面的盘子由a移动到c
            count++;
            System.out.println(String.format("第%d个盘从%c -> %c", num, a, c));
            //3. 将b柱上的num-1个盘子移动到c
            hanoiTower(num - 1, b, a, c);
        }
    }
}
